"""
给你二叉树的根节点 root 和一个整数目标和 targetSum ，找出所有 从根节点到叶子节点 路径总和等于给定目标和的路径。
叶子节点 是指没有子节点的节点。
示例 1：
输入：root = [5,4,8,11,null,13,4,7,2,null,null,5,1], targetSum = 22
输出：[[5,4,11,2],[5,8,4,5]]

示例 2：
输入：root = [1,2,3], targetSum = 5
输出：[]

示例 3：
输入：root = [1,2], targetSum = 0
输出：[]

链接：https://leetcode-cn.com/problems/path-sum-ii

"""
from mode import *

# 1
class Solution:
    def pathSum(self, root: TreeNode, targetSum: int) -> List[List[int]]:
        if not root:
            return []

        def dfs(node, target, temp):
            if not node:
                return

            target = target - node.val
            temp.append(node.val)
            if target == 0 and not node.left and not node.right:
                res.append(list(temp))

            dfs(node.left, target, temp)
            dfs(node.right, target, temp)
            temp.pop()

        res = []
        temp = []
        dfs(root, targetSum, temp)
        return res


# 2
class Solution1:
    def pathSum(self, root: TreeNode, targetSum: int) -> List[List[int]]:
        if not root:
            return []

        deque = collections.deque()
        deque.append(root)
        res = []
        temp = []
        while deque:
            size = len(deque)
            print(deque)
            for i in range(size):
                node = deque.popleft()
                targetSum -= node.val
                temp.append(node.val)

                if targetSum == 0 and not node.left and not node.right:
                    res.append(list(temp))

                if node.left:
                    deque.append(node.left)
                if node.right:
                    deque.append(node.right)

        return res


if __name__ == "__main__":
    rootList = '[5,4,8,11,null,13,4,7,2,null,null,5,1]'
    # rootList = '[1,2,3]'
    targetSum = 22
    root = generateTreeNode(rootList)

    A = Solution()
    print(A.pathSum(root, targetSum))

    A = Solution1()
    print(A.pathSum(root, targetSum))
